Organising information: ordered structures

Communication 1

Please, in your answers to the various exercises online, if you have to write a Python code, be sure that the correct indent is preserved by previewing your post before to publish it

You can use the ``` environment for defining your Python code:

```
write your Python code here
```

Communication 2 (cont.)

Clarification on test-driven development: all the tests must be passed in order to claim that an algorithm returns what it is expected

If a test execution return False, the test is not passed

If you need to check the non-compliancy of the execution of a function on purpose, then you have to create an additional testing function that returns True if the condition of the test is not passed

Communication 2

Remeber: first write the test, then develop the algorithm/function

Writing the right tests is very important since it would allow you to catch wrong behaviours of functions in presence of specific input values

However, to use only one test is not enough

Test your function by using different kinds of input, including the unusual ones, e.g. empty strings

Any question about the previous lecture?

Historic hero: Donald Knuth

Donald Knuth is a Computer Scientist

Main contributions: theoretical and practical development of the analysis of the computational complexity of algorithms, The Art of Computer Programming series of monographs, TeX typesetting system for writing academic documents

The Art of Computer Programming is an ongoing work (3 volumes and an half out of 7 have been published so far)

Preliminaries: Python functions

Definition of functions:
def <func_name>(<parameter_1>, ...)

It is the mechanism for implementing functions in Python, i.e. a mechanism for listing a sequence of instructions under a particular name

• Built-in functions: made available by the programming language itself, e.g. len() or list()

• User-defined functions: written by a user of the language for addressing some specific requirements or tasks that are not addressable by means of one built-in function directly, like the algorithm implemented in the previous lecture

Preliminaries: executions

def add_one(n):
    return n + 1

result = add_one(41)
print(result)

print(<object_1>, <object_2>, ...) allows one to print on screen one or more values (that can be referred by a variable)

Preliminaries: packages

Module: a Python file (extension .py) that contains the definition of variables, functions, and even runnable code

Package: a mechanism to expose one or more Python modules, functions, variables

from <package> import <module or function or variable>

from collections import deque

Data structures

The first volume of Knuth's series of books is entirely dedicated to a comprehensive introduction of all the basic data structures

A data structure is a way in which we can organise the information to process and returned by a computer, so as it can be accessed and modified in an efficient and computational manner

Broadly speaking, it is a sort of bucket where we can place some information, that provides some methods to add and retrieve pieces of such information

Order and repeatability

Among the simplest data structures, there are those ones that organise their item in a specific order and allow the repeatability of the values they contain

Order: the sequence in which the items are added to these data structures matters

Repeatability: the same value can appear twice or more times in the same data structure

List: example

List: definition

A list is a countable sequence of ordered and repeatable items

Countable: it is possible to know the length of the list (i.e. how many items it contains) – in Python, we can use the function len(<countable_object>)

Ordered: the items are placed in the list in a specific order, which is preserved

Repeatable: the items may appear more than one time in the list

List: methods

Create a new list: list()

Add new item: <list>.append(<item>)

Remove item: <list>.remove(<item>)

Add items from another list: <list>.extend(<another_list>)

Use methods on list

my_first_list = list()
my_first_list.append(34)
my_first_list.append(15)
my_first_list.append("Silvio")
my_first_list.remove(34)
my_first_list.extend(my_first_list)

my_first_list = 34 15 "Silvio" 15 "Silvio"

Stack: example

Stack: definition

A stack is a is a kind of list seen from a particular perspective, i.e. from bottom to top, and with a specific set of operations

The items follow a last in first out strategy (LIFO) for addition and removal

The last item inserted in the structure is placed in the top of the stack and, thus, it is also the first one that will be removed when requested

For removing the item in the middle of the stack one has to remove all the items that have been added after such middle item

Stack: methods

Create a new stack: deque()

Add new item: <stack>.append(<item>)

Remove (and return) latest item: <stack>.pop()

Add items from another stack: <stack>.extend(<another_stack>)

Use methods on stack

my_first_stack = deque()
my_first_stack.append(34)
my_first_stack.append(15)
my_first_stack.extend(my_first_stack)
my_first_stack.append("Silvio")
my_first_stack.pop()

Queue: example

Queue: definition

A queue is a is a kind of list seen from a particular perspective, i.e. from left to right, and with a specific set of operations

The items follow a first in first out strategy (FIFO) for addition and removal

The first item is placed in the left-most part of the queue and, thus, it is also the first one that will be removed when requested

For removing the item in the middle of the queue one has to remove all the items that have been added before such middle item

Queue: methods

Create a new queue: deque()

Add new item: <queue>.append(<item>)

Remove (and return) first item: <queue>.popleft()

Add items from another queue: <queue>.extend(<another_queue>)

Use methods on queue

my_first_queue = deque()
my_first_queue.append(34)
my_first_queue.append(15)
my_first_queue.append("Silvio")
my_first_queue.popleft()
my_first_queue.extend(my_first_queue)

my_first_queue = 34 15 "Silvio" 15 "Silvio"

Additional readings

From How To Code in Python:

• Chapter "How To Write Comments"
  All content
• Chapter "How To Import Modules"
  All content
• Chapter "Understanding Data Types"
  Section "Lists"
• Chapter "Understanding Lists"
  Introductory paragraphs and section "Indexing Lists"
• Chapter "How To Use List Methods"
  Introductory paragraphs and sections "list.append()", "list.extend()", "list.remove()"